/*******************************************************************************
 * Copyright (c) 2009, 2018 IBM Corp.
 *
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * and Eclipse Distribution License v1.0 which accompany this distribution.
 *
 * The Eclipse Public License is available at
 *    http://www.eclipse.org/legal/epl-v10.html
 * and the Eclipse Distribution License is available at
 *   http://www.eclipse.org/org/documents/edl-v10.php.
 *
 * Contributors:
 *    Ian Craggs - initial API and implementation and/or initial documentation
 *    Ian Craggs - use tree data structure instead of list
 *    Ian Craggs - change roundup to Heap_roundup to avoid macro name clash on MacOSX
 *******************************************************************************/

/**
 * @file
 * \brief functions to manage the heap with the goal of eliminating memory leaks
 *
 * For any module to use these functions transparently, simply include the Heap.h
 * header file.  Malloc and free will be redefined, but will behave in exactly the same
 * way as normal, so no recoding is necessary.
 *
 * */

#include "qnlink_config.h"

#include "Tree.h"
#include "Thread.h"
#include "log.h"

#if defined(HEAP_UNIT_TESTS)
char* Broker_recordFFDC(char* symptoms);
#endif /* HEAP_UNIT_TESTS */

//#ifndef __FILE_NAME__
//#define __FILE_NAME__ "Heap.c"
//#endif /* __FILE_NAME__ */
//#define Log(fmt, args...) printf("[QNLINK]%s:%d[%s()]"fmt"\n", __FILE_NAME__, __LINE__, __FUNCTION__, ##args)

#define Log(args...) LinkLogError(args)

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stddef.h>

#include "Heap.h"

#undef malloc
#undef realloc
#undef free
#undef calloc
#undef strdup
#undef strndup

#if defined(WIN32) || defined(WIN64)
mutex_type heap_mutex;
#else
static pthread_mutex_t heap_mutex_store = PTHREAD_MUTEX_INITIALIZER;
static mutex_type heap_mutex = &heap_mutex_store;
#endif

static heap_info state = { 0, 0 }; /**< global heap state information */
static int eyecatcher = 0x88888888;

/*#define HEAP_STACK 1 */

/**
 * Each item on the heap is recorded with this structure.
 */
typedef struct {
    char* file; /**< the name of the source file where the storage was allocated */
    int line; /**< the line no in the source file where it was allocated */
    void* ptr; /**< pointer to the allocated storage */
    size_t size; /**< size of the allocated storage */
#if defined(HEAP_STACK)
    char* stack;
#endif
} storageElement;

static Tree heap; /**< Tree that holds the allocation records */
static int gHeapInitialized = 0;

static size_t Heap_roundup(size_t size);
static int ptrCompare(void* a, void* b, int value);
/*static void Heap_check(char* string, void* ptr);*/
static void checkEyecatchers(char* file, int line, void* p, size_t size);
static int Internal_heap_unlink(char* file, int line, void* p);
static void HeapScan();

/**
 * Round allocation size up to a multiple of the size of an int.  Apart from possibly reducing fragmentation,
 * on the old v3 gcc compilers I was hitting some weird behaviour, which might have been errors in
 * sizeof() used on structures and related to packing.  In any case, this fixes that too.
 * @param size the size actually needed
 * @return the rounded up size
 */
static size_t Heap_roundup(size_t size)
{
    static int multsize = 4 * sizeof(int);

    if (size % multsize != 0)
        size += multsize - (size % multsize);
    return size;
}

/**
 * List callback function for comparing storage elements
 * @param a pointer to the current content in the tree (storageElement*)
 * @param b pointer to the memory to free
 * @return boolean indicating whether a and b are equal
 */
static int ptrCompare(void* a, void* b, int value)
{
    a = ((storageElement*) a)->ptr;
    if (value)
        b = ((storageElement*) b)->ptr;

    return (a > b) ? -1 : (a == b) ? 0 : 1;
}

/**
 * Allocates a block of memory.  A direct replacement for malloc, but keeps track of items
 * allocated in a list, so that free can check that a item is being freed correctly and that
 * we can check that all memory is freed at shutdown.
 * @param file use the __FILE__ macro to indicate which file this item was allocated in
 * @param line use the __LINE__ macro to indicate which line this item was allocated at
 * @param size the size of the item to be allocated
 * @return pointer to the allocated item, or NULL if there was an error
 */
void* mymalloc(char* file, int line, size_t size)
{
    storageElement* s = NULL;
    size_t space = sizeof(storageElement);
    size_t filenamelen = strlen(file) + 1;

    if (!gHeapInitialized) {
        return malloc(size);
    }

    Thread_lock_mutex(heap_mutex);
    size = Heap_roundup(size);
    if ((s = malloc(sizeof(storageElement))) == NULL) {
        Log("%s() Memory allocation error", __FUNCTION__);
        return NULL;
    }
    s->size = size; /* size without eyecatchers */
    if ((s->file = malloc(filenamelen)) == NULL) {
        Log("%s() Memory allocation error",  __FUNCTION__);
        free(s);
        return NULL;
}
    space += filenamelen;
    strcpy(s->file, file);
    #if defined(HEAP_STACK)
    #define STACK_LEN 300
    if ((s->stack = malloc(STACK_LEN)) == NULL)
    {
        Log("%s() Memory allocation error", __FUNCTION__);
        free(s->file);
        free(s);
        return NULL;
    }
    StackTrace_get(Thread_getid(), s->stack, STACK_LEN);
#endif
    s->line = line;
    /* Add space for eyecatcher at each end */
    if ((s->ptr = malloc(size + 2 * sizeof(int))) == NULL) {
        Log("%s() Memory allocation error", __FUNCTION__);
        free(s->file);
        free(s);
        return NULL;
    }
    space += size + 2 * sizeof(int);
    *(int*) (s->ptr) = eyecatcher; /* start eyecatcher */
    *(int*) (((char*) (s->ptr)) + (sizeof(int) + size)) = eyecatcher; /* end eyecatcher */
    TreeAdd(&heap, s, space);
    state.current_size += size;
    if (state.current_size > state.max_size)
        state.max_size = state.current_size;

    Thread_unlock_mutex(heap_mutex);
    return ((int*) (s->ptr)) + 1; /* skip start eyecatcher */
}


static void checkEyecatchers(char* file, int line, void* p, size_t size)
{
    int *sp = (int*) p;
    char *cp = (char*) p;
    int us;

    if ((us = *--sp) != eyecatcher)
        Log("%s() Invalid %s eyecatcher %d in heap item at file %s line %d", __FUNCTION__, "start", us, file, line);

    cp += size;
    if ((us = *(int*) cp) != eyecatcher)
        Log("%s() Invalid %s eyecatcher %d in heap item at file %s line %d", __FUNCTION__, "end", us, file, line);
}

/**
 * Remove an item from the recorded heap without actually freeing it.
 * Use sparingly!
 * @param file use the __FILE__ macro to indicate which file this item was allocated in
 * @param line use the __LINE__ macro to indicate which line this item was allocated at
 * @param p pointer to the item to be removed
 */
static int Internal_heap_unlink(char* file, int line, void* p)
{
    Node* e = NULL;
    int rc = 0;

    e = TreeFind(&heap, ((int*) p) - 1);
    if (e == NULL)
        Log("%s() Failed to remove heap item at file %s line %d", __FUNCTION__, file, line);
    else {
        storageElement* s = (storageElement*) (e->content);
        checkEyecatchers(file, line, p, s->size);
        /* free(s->ptr); */
        free(s->file);
        state.current_size -= s->size;
        TreeRemoveNodeIndex(&heap, e, 0);
        free(s);
        rc = 1;
    }
    return rc;
}

/**
 * Frees a block of memory.  A direct replacement for free, but checks that a item is in
 * the allocates list first.
 * @param file use the __FILE__ macro to indicate which file this item was allocated in
 * @param line use the __LINE__ macro to indicate which line this item was allocated at
 * @param p pointer to the item to be freed
 */
void myfree(char* file, int line, void* p)
{
    if (!gHeapInitialized) {
        free(p);
        return;
    }
    if (p) /* it is legal und usual to call free(NULL) */
    {
        Thread_lock_mutex(heap_mutex);
        if (Internal_heap_unlink(file, line, p))
            free(((int*) p) - 1);
        Thread_unlock_mutex(heap_mutex);
    } else {
        Log("%s() Call of free(NULL) in %s,%d", __FUNCTION__, file, line);
    }
}

/**
 * Remove an item from the recorded heap without actually freeing it.
 * Use sparingly!
 * @param file use the __FILE__ macro to indicate which file this item was allocated in
 * @param line use the __LINE__ macro to indicate which line this item was allocated at
 * @param p pointer to the item to be removed
 */
void Heap_unlink(char* file, int line, void* p)
{
    Thread_lock_mutex(heap_mutex);
    Internal_heap_unlink(file, line, p);
    Thread_unlock_mutex(heap_mutex);
}

/**
 * Reallocates a block of memory.  A direct replacement for realloc, but keeps track of items
 * allocated in a list, so that free can check that a item is being freed correctly and that
 * we can check that all memory is freed at shutdown.
 * We have to remove the item from the tree, as the memory is in order and so it needs to
 * be reinserted in the correct place.
 * @param file use the __FILE__ macro to indicate which file this item was reallocated in
 * @param line use the __LINE__ macro to indicate which line this item was reallocated at
 * @param p pointer to the item to be reallocated
 * @param size the new size of the item
 * @return pointer to the allocated item, or NULL if there was an error
 */
void *myrealloc(char* file, int line, void* p, size_t size)
{
    void* rc = NULL;
    storageElement* s = NULL;

    if (!gHeapInitialized) {
        return realloc(p, size);
    }

    Thread_lock_mutex(heap_mutex);
    s = TreeRemoveKey(&heap, ((int*) p) - 1);
    if (s == NULL)
        Log("%s() Failed to reallocate heap item at file %s line %d", __FUNCTION__, file, line);
    else {
        size_t space = sizeof(storageElement);
        size_t filenamelen = strlen(file) + 1;

        checkEyecatchers(file, line, p, s->size);
        size = Heap_roundup(size);
        state.current_size += size - s->size;
        if (state.current_size > state.max_size)
            state.max_size = state.current_size;
        if ((s->ptr = realloc(s->ptr, size + 2 * sizeof(int))) == NULL) {
            Log("%s() Memory allocation error", __FUNCTION__);
            return NULL;
        }
        space += size + 2 * sizeof(int) - s->size;
        *(int*) (s->ptr) = eyecatcher; /* start eyecatcher */
        *(int*) (((char*) (s->ptr)) + (sizeof(int) + size)) = eyecatcher; /* end eyecatcher */
        s->size = size;
        space -= strlen(s->file);
        s->file = realloc(s->file, filenamelen);
        space += filenamelen;
        strcpy(s->file, file);
        s->line = line;
        rc = s->ptr;
        TreeAdd(&heap, s, space);
    }
    Thread_unlock_mutex(heap_mutex);
    return (rc == NULL) ? NULL : ((int*) (rc)) + 1; /* skip start eyecatcher */
}

/**
 * Utility to find an item in the heap.  Lets you know if the heap already contains
 * the memory location in question.
 * @param p pointer to a memory location
 * @return pointer to the storage element if found, or NULL
 */
void* Heap_findItem(void* p)
{
    Node* e = NULL;

    Thread_lock_mutex(heap_mutex);
    e = TreeFind(&heap, ((int*) p) - 1);
    Thread_unlock_mutex(heap_mutex);
    return (e == NULL) ? NULL : e->content;
}

/**
 * Scans the heap and reports any items currently allocated.
 * To be used at shutdown if any heap items have not been freed.
 */
static void HeapScan()
{
    Node* current = NULL;

    Thread_lock_mutex(heap_mutex);
    Log("%s() Heap scan start, total %d bytes", __FUNCTION__, (int )state.current_size);
    while ((current = TreeNextElement(&heap, current)) != NULL) {
        storageElement* s = (storageElement*) (current->content);
        Log("%s() Heap element size %d, line %d, file %s, ptr %p", __FUNCTION__, (int )s->size, s->line, s->file, s->ptr);
        Log("  Content %.*s", (10 > current->size) ? (int )s->size : 10, (char* )(((int* )s->ptr) + 1));
    #if defined(HEAP_STACK)
        Log("  Stack:\n%s", s->stack);
    #endif
    }
    Log("%s() Heap scan end", __FUNCTION__);
    Thread_unlock_mutex(heap_mutex);
}

/**
 * Heap initialization.
 */
int Heap_initialize(void)
{
    int rc;
    Thread_lock_mutex(heap_mutex);
    if (!gHeapInitialized) {
        TreeInitializeNoMalloc(&heap, ptrCompare);
        heap.heap_tracking = 0; /* no recursive heap tracking! */
        gHeapInitialized = 1;
        rc = 0;
    } else {
        Log("%s() Heap has been initialized.", __FUNCTION__);
        rc = -1;
    }
    Thread_unlock_mutex(heap_mutex);
    return rc;
}

/**
 * Heap termination.
 */
void Heap_terminate(void)
{
    int mem_leak = 0;
    Thread_lock_mutex(heap_mutex);
    if (gHeapInitialized) {
        LinkLogDebug("%s() Maximum heap use was %d bytes", __FUNCTION__, (int )state.max_size);
        if (state.current_size > 0) {
            Log("%s() Some memory not freed at shutdown, possible memory leak", __FUNCTION__);
            mem_leak = 1;
        }
        gHeapInitialized = 0;
    } else {
        Log("%s() Heap no initialization.", __FUNCTION__);
    }
    Thread_unlock_mutex(heap_mutex);
    if (mem_leak) {
        HeapScan();
    }
}

/**
 * Access to heap state
 * @return pointer to the heap state structure
 */
heap_info* Heap_get_info(void)
{
    return &state;
}

/**
 * Dump a string from the heap so that it can be displayed conveniently
 * @param file file handle to dump the heap contents to
 * @param str the string to dump, could be NULL
 */
int HeapDumpString(FILE* file, char* str)
{
    int rc = 0;
    size_t len = str ? strlen(str) + 1 : 0; /* include the trailing null */

    if (fwrite(&(str), sizeof(char*), 1, file) != 1)
        rc = -1;
    else if (fwrite(&(len), sizeof(int), 1, file) != 1)
        rc = -1;
    else if (len > 0 && fwrite(str, len, 1, file) != 1)
        rc = -1;
    return rc;
}

/**
 * Dump the state of the heap
 * @param file file handle to dump the heap contents to
 */
int HeapDump(FILE* file)
{
    int rc = 0;
    Node* current = NULL;

    while (rc == 0 && (current = TreeNextElement(&heap, current))) {
        storageElement* s = (storageElement*) (current->content);

        if (fwrite(&(s->ptr), sizeof(s->ptr), 1, file) != 1)
            rc = -1;
        else if (fwrite(&(current->size), sizeof(current->size), 1, file) != 1)
            rc = -1;
        else if (fwrite(s->ptr, current->size, 1, file) != 1)
            rc = -1;
    }
    return rc;
}

void* mycalloc(char* file, int line, size_t nmemb, size_t size)
{
    void* mem_ptr = mymalloc(file, line, nmemb * size);
    if (mem_ptr) {
        memset(mem_ptr, 0x00, nmemb * size);
    }
    return mem_ptr;
}

/* Make Valgrind Happy */
char* mystrdup(char* file, int line, const char* src)
{
    size_t mlen = strlen(src) + 1;
    char* temp = mymalloc(file, line, mlen);
    memset(temp, '\0', mlen);
    strncpy(temp, src, mlen);
    return temp;
}

char* mystrndup(char* file, int line, const char* src, size_t n)
{
    size_t mlen = n + 1;
    char* temp = mymalloc(file, line, mlen);
    memset(temp, '\0', mlen);
    strncpy(temp, src, n);
    return temp;
}

#if defined(HEAP_UNIT_TESTS)

void Log(enum LOG_LEVELS log_level, int msgno, char* format, ...)
{
    printf("Log %s", format);
}

char* Broker_recordFFDC(char* symptoms)
{
    printf("recordFFDC");
    return "";
}

#define malloc(x) mymalloc(__FILE__, __LINE__, x)
#define realloc(a, b) myrealloc(__FILE__, __LINE__, a, b)
#define free(x) myfree(__FILE__, __LINE__, x)

int main(int argc, char *argv[])
{
    char* h = NULL;
    Heap_initialize();

    h = malloc(12);
    free(h);
    printf("freed h\n");

    h = malloc(12);
    h = realloc(h, 14);
    h = realloc(h, 25);
    h = realloc(h, 255);
    h = realloc(h, 2225);
    h = realloc(h, 22225);
    printf("freeing h\n");
    free(h);
    Heap_terminate();
    printf("Finishing\n");
    return 0;
}

#endif /* HEAP_UNIT_TESTS */

/* Local Variables: */
/* indent-tabs-mode: t */
/* c-basic-offset: 8 */
/* End: */
